/*
    折半插入排序，如果是线性表（数组存储，可以随机访问），那么在往左寻找合适的位置的时候
    可以使用二分法
*/
#include<stdio.h>
const int numbers_size=8;
int numbers[]={49,38,65,97,76,13,27,49};
void insertSort(int array[],int n){
    if(n<2) return;//0个元素或1个元素直接返回
    int i,j;//元素下标
    int left,right,mid;//二分查找
    //从左往右排序，第一个元素就一个，也就是自然有序，所以从第二个元素开始排
    for(int i=1;i<n;i++){
        int key=array[i];//保存当前待插入的元素
        left=0;right=i-1;//插入位置是0到i-1的范围
        /*
            这里给出一个下标的计算实例：38 49 65 76 97 13 27 49 ,待排序的元素是13,下标为5
            此时left=0,right=4，mid=2，下标2的元素为65，比13大
            left=0,right=mid-1=1, mid=0 下标0的元素是38，比13大
            left=0,right=mid-1 = -1 此时while循环退出，目标所在下标可以是right+1，这个例子不太好
        */
        while(left<=right){//while循环用来查找下标，最后位置应该是right所在的位置
            mid=(left+right)/2;
            if(array[mid]>key){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        for(int j=i-1;j>=left;--j){//同理这里的left可以改成right+1
            array[j+1]=array[j];
        }
        array[left]=key;//和array[right+1]=key等同，这里应该是向下取整的原因
        show(numbers,numbers_size);
    }
}

void show(int array[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}

int main(void){
    insertSort(numbers,numbers_size);
    show(numbers,numbers_size);
}